import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.function.IntFunction;

public class MaxOfSlidingWindow {
    /*
    * ---------------需要时常复习----------------
    * 滑动窗口最大值
    * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
    * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
    * 返回 每个滑动窗口中的最大值 。
    *
    * 提示：
    * 1 <= nums.length <= 105
    * -104 <= nums[i] <= 104
    * 1 <= k <= nums.length
    * */
    public static void main(String[] args){
        MaxOfSlidingWindow o = new MaxOfSlidingWindow();
        int[] res = o.solution(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
        for (int i : res){
            System.out.print(i+" ");
        }
    }

    // 我的想法：使用栈来存放结果，每滑动一次和栈顶元素比较，在存活时间不为0的情况下，大则放入，小则复制栈顶元素
    // 结果是，时间巨慢，空间开销大
    public int[] mySolution(int[] nums, int k){
        Deque<Integer> deque = new ArrayDeque();
        int live = 0;
        for (int i = 0; i <= nums.length - k; i++) {
            if(live == 0){  // 存活时间为0, 需要计算新的最大值
                int max = Integer.MIN_VALUE;
                for (int j = 0; j < k; j++) {
                    int cur = nums[i+j];
                    if(cur >= max){
                        max = cur;
                        live = j + 1;   // 更新存活时间
                    }
                }
                deque.add(max);
            }
            else {  // 栈顶最大值尚存，直接比较新进入窗口的值
                int cur = nums[i+k-1];
                if(deque.peekLast() > cur)
                    deque.add(deque.peekLast());
                else {
                    deque.add(cur);
                    live = k;   // 更新存活时间
                }
            }
            live--;
        }
        int[] res = deque.stream().mapToInt(Integer::valueOf).toArray();
        return res;
    }

    // 使用单调队列， 维护一个队列，使这个队列的头始终是最大值就好
    public int[] solution(int[] nums, int k){
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        for (int i = 0; i < k; i++) {   // 先把前k个值装进单调队列
            while (!deque.isEmpty() && nums[i] > deque.peekLast())  // 使加入队尾的元素一定是最小
                deque.pollLast();
            deque.add(nums[i]);
        }
        res[index++] = deque.peek();
        for (int i = k; i < nums.length; i++) { // 开始滑动窗口
            // 弹出掉到窗口外的元素，如果这个元素是最大的话
            if(nums[i-k] == deque.peek())
                deque.pollFirst();
            // 加入新进入窗口的元素
            while (!deque.isEmpty() && nums[i] > deque.peekLast())  // 使加入队尾的元素一定是最小
                deque.pollLast();
            deque.add(nums[i]);
            // 写入结果，此时的队头一定最大
            res[index++] = deque.peek();
        }
        return res;
    }
}
